package com.shm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 1008. 前序遍历构造二叉搜索树
 * 返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
 * <p>
 * (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）
 * <p>
 * 题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * 输入：[8,5,1,7,10,12]
 * 输出：[8,5,10,1,7,null,12]
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= preorder.length <= 100
 * 1 <= preorder[i] <= 10^8
 * preorder 中的值互不相同
 *
 * @author SHM
 */
public class BstFromPreorder {
    int[] preorder;
    int n;
    int idx = 0;

    /**
     * 方法二：递归
     * 分析
     * <p>
     * 当我们将先序遍历排序得到中序遍历时，我们花费了 O(N \log N)O(NlogN) 的时间复杂度，但事实上并没有得到任何额外的信息。也就是说，我们可以直接跳过生成中序遍历的步骤，根据先序遍历直接构造出二叉树。注意，由于题目中的二叉树是二叉搜索树，因此根据先序遍历构造出的二叉树才是唯一的。
     * <p>
     * 我们使用递归的方法，在扫描先序遍历的同时构造出二叉树。我们在递归时维护一个 (lower, upper) 二元组，表示当前位置可以插入的节点的值的上下界。如果此时先序遍历位置的值处于上下界中，就将这个值作为新的节点插入到当前位置，并递归地处理当前位置的左右孩子的两个位置。否则回溯到当前位置的父节点。
     * <p>
     * 算法
     * <p>
     * 将 lower 和 upper 的初始值分别设置为负无穷和正无穷，因为根节点的值可以为任意值。
     * <p>
     * 从先序遍历的第一个元素 idx = 0 开始构造二叉树，构造使用的函数名为 helper(lower, upper)：
     * <p>
     * 如果 idx = n，即先序遍历中的所有元素已经被添加到二叉树中，那么此时构造已经完成；
     * <p>
     * 如果当前 idx 对应的先序遍历中的元素 val = preorder[idx] 的值不在 [lower, upper] 范围内，则进行回溯；
     * <p>
     * 如果 idx 对应的先序遍历中的元素 val = preorder[idx] 的值在 [lower, upper] 范围内，则新建一个节点 root，并对其左孩子递归处理 helper(lower, val)，对其右孩子递归处理 helper(val, upper)。
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(N)O(N)，仅扫描前序遍历一次。
     * <p>
     * 空间复杂度：O(N)O(N)，用来存储二叉树。
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/solution/jian-kong-er-cha-shu-by-leetcode/
     *
     * @param preorder
     * @return
     */
    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder = preorder;
        n = preorder.length;
        return helper(Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    TreeNode helper(int lower, int upper) {
        if (idx == n) {
            return null;
        }
        int val = preorder[idx];
        if (val < lower || val > upper) {
            return null;
        }

        idx++;
        TreeNode node = new TreeNode(val);
        node.left = helper(lower, val);
        node.right = helper(val, upper);
        return node;
    }

    /**
     * 方法三：迭代
     * 方法二中的递归可以通过添加一个栈变成迭代。
     * <p>
     * 将先序遍历中的第一个元素作为二叉树的根节点，即 root = new TreeNode(preorder[0])，并将其放入栈中。
     * <p>
     * 使用 for 循环迭代先序遍历中剩下的所有元素：
     * <p>
     * 将栈顶的元素作为父节点，当前先序遍历中的元素作为子节点。如果栈顶的元素值小于子节点的元素值，则将栈顶的元素弹出并作为新的父节点，直到栈空或栈顶的元素值大于子节点的元素值。注意，这里作为父节点的是最后一个被弹出栈的元素，而不是此时栈顶的元素；
     * <p>
     * 如果父节点的元素值小于子节点的元素值，则子节点为右孩子，否则为左孩子；
     * <p>
     * 将子节点放入栈中。
     * 复杂度分析
     * <p>
     * 时间复杂度：O(N)O(N)，仅扫描前序遍历一次。
     * <p>
     * 空间复杂度：O(N)O(N)，用来存储栈和二叉树。
     * <p>
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/solution/jian-kong-er-cha-shu-by-leetcode/
     *
     * @param preorder
     * @return
     */
    public TreeNode bstFromPreorder_2(int[] preorder) {
        int n = preorder.length;
        if (n == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        for (int i = 1; i < n; i++) {
            TreeNode node = deque.peek();
            TreeNode child = new TreeNode(preorder[i]);
            while (!deque.isEmpty() && deque.peek().val < child.val) {
                node = deque.pop();
            }
            if (node.val < child.val) {
                node.right = child;
            } else {
                node.left = child;
            }

            deque.push(child);
        }
        return root;
    }
}
